package leetcodecompetition.S105;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @Author: Siantar
 * @Date: 2023-05-27-22:36
 * @Description: 1.0
 */
public class T6394 {
    String[] dictionary;
    String s;
    int[] arr;

    public int minExtraChar(String s, String[] dictionary) {
        this.s = s;
        this.dictionary = dictionary;
        this.arr = new int[s.length()];
        Arrays.fill(arr, -1);
        return minExtraCharHelper(0);
    }

    public int minExtraCharHelper(int d) {
        if (d == s.length()) return 0;
        if (arr[d] != -1) return arr[d];
        int min = minExtraCharHelper(d + 1) + 1;
        for (String dict : dictionary) {
            if (s.charAt(d) == dict.charAt(0) && s.indexOf(dict, d) == d) {
                min = Math.min(min, minExtraCharHelper(d + dict.length()));
            }
        }
        arr[d] = min;
        return min;
    }
    @Test
    public void test() {
        System.out.println(minExtraChar("enknouowgowcipfipojlrpuowgoiogiiebfjiafwksaigjyd",new String[]{"gw","lq","yzqch","sah","giieb","kfqczw","qxqz","jb","ucxmpe","hpwr","y","vzlhe","i","kn","ip","iafwk","zl","dw","yhxeqi","egktb","xasq","f","c","vrllz","p","uowgo","pgxd","gnjgkm","rnug","sa","vfccq","j"}
        ));
    }
}
